package th.retrofit.lib;

import java.util.List;

/**
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表
 */
public class Solution23 {

    public ListNode mergeKLists(ListNode[] lists) {
        int length = lists.length;
        if (length == 0) return null;
        if (length == 1) return lists[0];
        int end = (length + 1) / 2;
        ListNode[] newLists = new ListNode[end];
        for (int i = 0; i < end; i++) {
            int bIndex = i * 2;
            int eIndex = bIndex + 1;
            if (eIndex < length) {
                newLists[i] = mergeTwoLists(lists[bIndex], lists[eIndex]);
            } else {
                newLists[i] = lists[bIndex];
            }
        }
        return mergeKLists(newLists);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode l3 = new ListNode(2, new ListNode(6));

//        System.out.println(new Solution23().mergeTwoLists(l1, l2));
        System.out.println(new Solution23().mergeKLists(new ListNode[]{l1, l2, l3}));
    }

}
